package io.gitee.wiqer.simple;

import java.util.Arrays;

/**
 * 描述
 * 给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。
 *
 * 数据范围： 0 \le n \le 50000≤n≤5000， 0 \le len(strs_i) \le 50000≤len(strs
 * i
 * ​
 *  )≤5000
 * 进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 */
public class SolutionNC55_LongestCommonPrefix {
    /**
     *解法一：纵向扫描
     * 将字符串数组看作一个二维空间，每一次从第一列开始。
     * 确定所有字符子串中第一列字符。
     * 逐层扫描后面每一列，遇到不同字符停止扫描。
     * @param strs string字符串一维数组
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {

        if (strs == null || strs.length == 0) {
            return "";
        }

        //charAt() 方法用于返回指定索引处的字符。索引范围为从 0 到 length() - 1。所以这里不能 减去1 后续循环是0----length()-1 所以正好
        int row = strs.length;

        int column = strs[0].length();

        String maxCommonPrefix = "";

        for (int columnIndex = 0; columnIndex < column; columnIndex++) {

            char targetColumnChar = strs[0].charAt(columnIndex);

            for (int rowIndex = 1; rowIndex < row; rowIndex++) {

                //strs[rowIndex].length() == columnIndex 即:如当第二行为["c",""]时,直接结束即可 或者 ["cc","c"] 当遍历到第2个C 即index = 1时 此时再遍历第二行的字符串时,发现已经是第2个字符串的总长度 直接结束
                if (strs[rowIndex].length() == columnIndex || strs[rowIndex].charAt(columnIndex) != targetColumnChar) {
                    return strs[0].substring(0, columnIndex);
                }
            }
        }

        //各行各列都相等的情况 返回第一个字符串即可 或者 ["c","c"] 只有一行的情况 返回数组中的第一个
        return strs[0];
    }

    /**
     * 解法一：排序
     * 计算二进制
     * @param strs
     * @return
     */
    public String longestCommonPrefix_Sort (String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        // write code here
        Arrays.sort(strs);
        String temp =null;
        for (int i = 0; i < strs[0].length()&&i < strs[1].length(); i++) {
            if (strs[0].charAt(i) !=strs[1].charAt(i)  ) {
                temp= new String(strs[0].toCharArray(),0,i);
            }
        }
        if (temp == null) {
            return strs[0];
        }else {
            return longestCommonPrefix ( new String[]{temp,strs[strs.length - 1]});
        }
    }
}
